// https://www.lintcode.com/problem/decrypt-the-string/

public class Solution {
    /**
     * @param Message: the string xiao Q sent to xiao A.
     * @return: the string after decompress
     */
    public String DecompressString(String Message) {
        // 
        Stack<String> ret = new Stack<>();
        Stack<String> stack = new Stack<>();
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < Message.length()) {
            Character c = Message.charAt(i);
            ++i;
            if ((c != '[') && (c != ']') && (c != '|')) {
                sb.append(c);
            } else {
                if (sb.length() > 0) {
                    stack.add(sb.toString());
                }
                stack.add(Character.toString(c));
                sb.setLength(0);
            }
        }
        if (sb.length() > 0) {
            stack.add(sb.toString());
        }
        for (String s : stack) {
            if (!s.equals("]")) {
                ret.add(s);
            } else if (s.equals("]")) {
                String v0 = ret.pop();
                String v1 = ret.pop();
                while (!v1.equals("|")) {
                    v0 = v1 + v0;
                    v1 = ret.pop();
                }
                int v2 = 0;
                if (v1.equals("|")) {
                    String count = ret.pop();
                    v2 = Integer.valueOf(count);
                }
                ret.pop(); // 弹出'['
                if (v2 > 0) {
                    String v0s = "";
                    while (v2 > 0) {
                        v0s += v0;
                        --v2;
                    }
                    ret.add(v0s);
                } else {
                    ret.add(v0);   
                }
            }
        }
        sb.setLength(0);
        for (String s : ret) {
            sb.append(s);
        }
        return sb.toString();
    }
}